No todos los Lenguajes son Regulares

Un autómata finito que aceptara el lenguaje L={a^kb^k | k ≥ 0} tendría que contar el número de 'a' en cada cadena para asegurarse de que el número de 'b' es el mismo. No hay límite a cuanto el autómata tendría que contar para aceptar una cadena de este lenguaje. Pero un autómata con memoria finita solo puede contar en proporción al tamaño de su memoria: el número de sus estados.

Ese es un argumento intuitivo de por qué este lenguaje no es regular, pero no es una prueba. Para probar que un lenguaje no es regular usamos un resultado llamado el lema de bombeo para lenguajes regulares.

El Lema de Bombeo

Sea L un lenguaje regular. Existe un entero n tal que para cualquier w ∈ L con |w| ≥ n (la longitud de w es mayor o igual a n), w puede ser escrita como xyz, cumpliendo con las siguientes condiciones:

1. |xy| ≤ n
2. |y| ≥ 1
3. xyⁱz ∈ L ∀ i ≥ 1

Comprobación Intuitiva

Todo lenguaje regular es aceptado por un autómata finito determinista. Si dicho autómata posee n estados, entonces cualquier paso de longitud n debe visitar por lo menos n+1 estados, y por lo tanto contiene un ciclo.

En Resumen

• Si un lenguaje infinito es regular, es, por ser regular, aceptado por un AFD.
• El DFA tiene un número finito de estados, digamos, n.
• Ya que el lenguaje es infinito, algunas cadenas en el mismo deben tener longitud mayor que n.
• Para que una cadena de longitud mayor que n sea aceptada por el AFD, el camino a través de los estados del autómata debe contener un ciclo.
• Repetir el ciclo un número arbitrario de veces debe producir otra cadena aceptada por el AFD.

Cómo usar el Lema de Bombeo

El Lema de Bombeo describe una propiedad  de todos los lenguajes regulares infinitos. Si podemos mostrar que un lenguaje no posee esta propiedad, sabemos entonces que el lenguaje no es regular.

La estrategia a usar es la prueba por contradicción (reducción al absurdo). Asumimos que el lenguaje en cuestión posee la propiedad descrita por el Lema de Bombeo, y luego mostramos que eso produce una contradicción. Dada la contradicción, se concluye que el lenguaje no es regular.

Ejemplos de Lenguajes No Regulares

L={a^kb^k  | k ≥ 0}

Suponemos que existe n. Tomamos la cadena aⁿbⁿ que pertenece al lenguaje. La parte a repetir, y, tiene que consistir en una o más a. Repitiendo a's, (yⁱ) no obtenemos nuevas cadenas pertenecientes al lenguaje, por lo tanto el lenguaje no es regular.

1. L={ww^R | w ∈ Σ^*} donde w^R significa el reverso de a cadena w.
2. L={w ∈ {a,b}^* | w contiene el mismo número de a y b}
3. L={ww | w ∈ Σ^*}